package docker

//分布式存储之一致性哈希算法

/*

目录：
	1.背景
	2.目的
	3.实现的步骤
		3.1 算法构建一致性哈希环
		3.2 服务器ip节点映射
		3.3 key落到服务器的落键规则
	4.优点
		4.1 一致性哈希算法的容错性
		4.2 一致性哈希算法的扩展性
	5.缺点
		5.1一致性算法的数据倾斜问题
		5.2 为解决数据倾斜问题，引入虚拟节点机制
	6.小总结




--------------------------------------1.背景--------------------------------------

	背景
		一致性哈希算法在1997年由麻省理工学院中提出的，设计目标是为了解决
		【分布式缓存数据】【变动和映射】问题，某个机器宕机了，分母数量改变了，自然取余数不OK了。






--------------------------------------2.目的--------------------------------------
	目的
		提出一致性Hash解决方案。
		目的是当服务器个数发生变动时，尽量减少影响客户端到服务器的映射关系





--------------------------------------3.实现的步骤--------------------------------------
	三大步骤：
		1.算法构建一致性哈希环
		2.服务器ip节点映射
		3.key落到服务器的落键规则



---------1.算法构建一致性哈希环---------
	看图 images/docker-1002-分布式算法：一致性哈希环-01.png

		一致性算法哈希环

		一致性哈希算法必然有个hash函数并按照算法产生hash值，这个算法的所有可能哈希值会构成一个【全量集】，
		这个集合可以成为一个hash空间[0,2^32-1]，这个是一个【线性空间】，
		但是在算法中，我们通过适当的逻辑控制将它首尾相连(0=2^32)这样让它逻辑上形成了一个【环形空间】。


		它也是按照使用取模的方法，前面笔记介绍的节点取模法是对节点（服务器〉的数量进行取模。
		而一致性Hash算法是对2^32取模，简单来说，
		一致性Hash算法将整个哈希值空间组织成一个虚拟的圆环，如假设某哈希函数H的值空间为0-2^32-1(即哈希值是一个32位无符号整形），
		整个哈希环如下图:
			images/docker-1002-分布式算法：一致性哈希环-01.png
		整个空间按顺时针方向组织，圆环的正上方的点代表0,0点右侧的第一个点代表1，以此类推，2、3、4、……直到2^32-1，
		也就是说0点左侧的第一个点代表2^32-1，0和2^32-1在零点中方向重合，我们把这个【由2^32个点组成的圆环称为Hash环】。



		以前 【哈希取余/节点取余法】是对节点(服务器)的数量进行取模/余【 hash(key)% N 】
		而
		一致性hash算法是对2^23取余/模
		一致性hash算法将整个哈希值空间组织成一个虚拟的圆环。


		所以，无论有多少个机器，结果都在环中，新增或减少都不会印象这个环，就像一口大锅，多一点，少一点，结果都在是这个锅里


---------2.服务器ip节点映射---------
	看图 images/docker-1003-分布式算法：一致性哈希环-02-服务器ip节点映射.png


	节点映射
	将集群中各个IP节点映射到环上的某一个位置。
	将各个服务器使用Hash进行一个哈希，具体可以选择服务器的IP或主机名作为关键字进行哈希，这样每台机器就能确定其在哈希环上的位置。
	假如4个节点NodeA、B、C、D，经过IP地址的哈希函数计算(hash(ip))，使用IP地址哈希后在环空间的位置如下:

		看图 images/docker-1003-分布式算法：一致性哈希环-02-服务器ip节点映射.png



---------3.key落到服务器的落键规则---------
	看图 images/docker-1004-分布式算法：一致性哈希环-03-key落到服务器的落键规则.png


	key落到服务器的落键规则

	当我们需要存储一个kv键值对时，首先计算key的hash值，hash(key)，
	将这个key使用相同的函数Hash计算出哈希值并确定此数据在环上的位置，
	【从此位置沿环顺时针“行走”】，第一台遇到的服务器就是其应该定位到的服务器，并将该键值对【存储在该节点上】。

	如我们有Object A、Object B、Object C、ObjectD四个数据对象，经过哈希计算后，在环空间上的位置如下:
		看图 images/docker-1004-分布式算法：一致性哈希环-03-key落到服务器的落键规则.png
		看图 images/docker-1005-分布式算法：一致性哈希环-04-key落到服务器的落键规则.png

	根据一致性Hash算法，数据A会被定为到Node A上，B被定为到Node B上，C被定为到Node C上，D被定为到Node D上。






--------------------------------------4.优点--------------------------------------

	优点：
		1.一致性哈希算法的容错性
		2.一致性哈希算法的扩展性



---------1.一致性哈希算法的容错性---------

	容错性
	假设Node C宕机，可以看到此时对象A、B、D不会受到影响，只有C对象被重定位到Node D。
	一般的，在一致性Hash算法中，如果一台服务器不可用，则【受影响的数据仅仅是此服务器到其环空间中前一台服务器（即沿着逆时针方向行走遇到的第一台服务器）之间数据】，其它不会受到影响。
	简单说，就是C挂了，受到影响的只是B、C之间的数据，并且这些数据会转移到D进行存储。

	看图
		images/docker-1006-哈希算法：一致性哈希环算法的容错性-01.png
		images/docker-1007-哈希算法：一致性哈希环算法的容错性-02.png



---------2.一致性哈希算法的扩展性---------


	扩展性
	数据量增加了，需要增加一台节点NodeX，X的位置在A和B之间，
	那收到影响的也就是A到X之间的数据，重新把A到X的数据录入到X上即可，不会导致hash取余全部数据重新洗牌。

	看图
		images/docker-1008-哈希算法：一致性哈希环算法的扩展性-01.png

	举例：
		A--1000w-->B 之间有一千万数据
		现在插入一个节点x
		A--500w-->X--500w-->B
		加入x在ab的中间，只需要把a-x中间的500w数据移动到节点x上，而x到b的节点数据不需要移动






--------------------------------------5.缺点--------------------------------------

	缺点
		5.1一致性算法的数据倾斜问题

		看图 images/docker-1009-哈希算法：一致性哈希环算法的数据倾斜问题.png


	Hash环的数据倾斜问题
	一致性Hash算法在服务节点太少时，容易因为节点分布不均匀而造成数据倾斜（被缓存的对象大部分集中缓存在某一台服务器上）问题，

	例如系统中只有两台服务器:
		看图 images/docker-1009-哈希算法：一致性哈希环算法的数据倾斜问题.png

	此时只有两台机器，大部分都会集中到节点a上，造成数据倾斜的问题




		5.2 虚拟节点机制

	为了解决数据分布不均匀的问题，一致性哈希算法引入【虚拟节点机制】。

	虚拟节点是实际节点（机器）在哈希空间的【复制】，【每个实际节点】（机器）对应【若干个虚拟节点】。





--------------------------------------6.小总结--------------------------------------

	小总结

	为了在【节点数目发生改变】时【尽可能少的迁移数据】
	将所有的存储节点排列在收尾相接的Hash环上，每个key在计算Hash后会【顺时针】找到临近的存储节点存放。
	而当有节点加入或退出时仅影响该节点在Hash环上【顺时针相邻】的后续节点。


	优点
	加入和删除节点只影响哈希环中顺时针方向的相邻的节点，对其他节点无影响。

	缺点
	数据的分布和节点的位置有关，因为这些节点不是均匀的分布在哈希环上的，所以数据在进行存储时达不到均匀分布的效果。







*/
